0299. 猜数字游戏【中等】
1. 📝 题目描述
你在和朋友一起玩 猜数字(Bulls and Cows) 游戏,该游戏规则如下:
写出一个秘密数字,并请朋友猜这个数字是多少。朋友每猜测一次,你就会给他一个包含下述信息的提示:
- 猜测数字中有多少位属于数字和确切位置都猜对了(称为 "Bulls",公牛),
- 有多少位属于数字猜对了但是位置不对(称为 "Cows",奶牛)。也就是说,这次猜测中有多少位非公牛数字可以通过重新排列转换成公牛数字。
给你一个秘密数字 secret 和朋友猜测的数字 guess,请你返回对朋友这次猜测的提示。
提示的格式为 "xAyB",x 是公牛个数, y 是奶牛个数,A 表示公牛,B 表示奶牛。
请注意秘密数字和朋友猜测的数字都可能含有重复数字。
示例 1:
txt
输入:secret = "1807", guess = "7810"
输出:"1A3B"
解释:数字和位置都对(公牛)用 '|' 连接,数字猜对位置不对(奶牛)的采用斜体加粗标识。
"1807"
|
"7810"1
2
3
4
5
6
2
3
4
5
6
示例 2:
txt
输入:secret = "1123", guess = "0111"
输出:"1A1B"
解释:数字和位置都对(公牛)用 '|' 连接,数字猜对位置不对(奶牛)的采用斜体加粗标识。
"1123" "1123"
| or |
"0111" "0111"
注意,两个不匹配的 1 中,只有一个会算作奶牛(数字猜对位置不对)。通过重新排列非公牛数字,其中仅有一个 1 可以成为公牛数字。1
2
3
4
5
6
7
2
3
4
5
6
7
提示:
1 <= secret.length, guess.length <= 1000secret.length == guess.lengthsecret和guess仅由数字组成
2. 🎯 s.1 - 一次遍历
c
char* getHint(char* secret, char* guess) {
int bulls = 0, cows = 0;
int count[10] = {0};
for (int i = 0; secret[i]; i++) {
if (secret[i] == guess[i]) {
bulls++;
} else {
if (count[secret[i] - '0']++ < 0) cows++;
if (count[guess[i] - '0']-- > 0) cows++;
}
}
char* res = (char*)malloc(20);
sprintf(res, "%dA%dB", bulls, cows);
return res;
}1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
2
3
4
5
6
7
8
9
10
11
12
13
14
15
js
/**
* @param {string} secret
* @param {string} guess
* @return {string}
*/
var getHint = function (secret, guess) {
let bulls = 0,
cows = 0
const count = new Array(10).fill(0)
for (let i = 0; i < secret.length; i++) {
if (secret[i] === guess[i]) {
bulls++
} else {
if (count[secret[i]]++ < 0) cows++
if (count[guess[i]]-- > 0) cows++
}
}
return `${bulls}A${cows}B`
}1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
py
class Solution:
def getHint(self, secret: str, guess: str) -> str:
bulls = cows = 0
count = [0] * 10
for s, g in zip(secret, guess):
if s == g:
bulls += 1
else:
if count[int(s)] < 0:
cows += 1
count[int(s)] += 1
if count[int(g)] > 0:
cows += 1
count[int(g)] -= 1
return f"{bulls}A{cows}B"1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
2
3
4
5
6
7
8
9
10
11
12
13
14
15
- 时间复杂度:
,其中 是字符串长度 - 空间复杂度:
,计数数组固定大小 10
算法思路:
- 同位置相同即为 Bull,否则用计数数组统计匹配
- secret 的数字使计数 +1,guess 的数字使计数 -1
- 若 secret 数字对应计数 < 0 说明之前 guess 已记录过,cows++;反之亦然